<?php

/*
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1], 
Table[i][j] ≤ Table[i + 1][j]

Note:
Any element in the table is always larger than the elements above and to the left of it.
So if the search is larger than the search, we can discard the elements to its left and above.

Starting from the top right corner:
1) If search > element, we discard the first row (because the rest are all smaller) and move down
2) Else if search < element, we discard the last column (because they are all larger) and move left
3) The result is that we are looking at the new element at the top right corner of the new table' (after discarding column/row)
4) repeat the process until we find the element.

The same can be applied when starting from the left bottom corner.

*/

// Input for a 10 by 10 array
$input = "1 2 10 17 19 21 24 29 38 46 55 61 70 78 80 89 90 101 107 109 112 122 133 137 141 142 143 147 148 159 167 168 173 178 184 189 192 196 198 206 207 217 227 232 240 246 254 264 270 273 274 275 284 290 299 302 310 312 319 324 332 341 351 352 360 370 375 386 394 403 411 416 427 434 444 451 461 462 472 477 485 492 495 499 509 513 520 531 541 545 546 552 558 566 575 580 585 593 596 598";

$array = explode( ' ', $input );

$search = $array[ rand(0, 99) ];

echo count($array)." elements.<br/>";

$table = array_chunk( $array, 10 );

echo "Table:<br/>";
echo "<div>";
for( $i=0; $i<10; $i++ ){
	for( $j=0; $j<10; $j++ ){
		echo "<div style='float:left;width:50px;text-align:right;display:inline-block'>".$table[$i][$j]."</div>";
	}
	echo "<br/>";
}
echo "</div>";

searchTwoDSortedArray2( $search, $table );

// Search from top right
function searchTwoDSortedArray( $search, $table ){
	$i = 0;
	$j = 9;
	$found = false;
	while( $i<10 && $j>=0 ){
		$element = $table[$i][$j];
		echo "Passing element $element<br/>";
		if( $search > $element ){
			$i++;
		}
		else if( $search < $element ){
			$j--;
		}
		else {
			echo "Found $search at row $i column $j!!!";
			$found = true;
			break;
		}
	}
	if( !$found ){
		echo "$search not found...";
	}

}

// Search from bottom left
function searchTwoDSortedArray2( $search, $table ){
	$i = 9;
	$j = 0;
	$found = false;
	while( $i>=0 && $j<10 ){
		$element = $table[$i][$j];
		echo "Passing element $element<br/>";
		if( $search > $element ){
			$j++;
		}
		else if( $search < $element ){
			$i--;
		}
		else {
			echo "Found $search at row $i column $j!!!";
			$found = true;
			break;
		}
	}
	if( !$found ){
		echo "$search not found...";
	}

}